Due to its large scope of potential applications the automation of the drawing of two-dimensional graphs has received a considerable attention over the past decades, resulting in the publication of a countless number of papers by the engineering and academic communities describing methods and techniques to draw graphs, often for a particular context. Nevertheless, the drawing of graphs in the general case remains a very hard problem for which a single best solution does not exist. Typical of the publications made on this subject is a paper by Gansner and al. from AT&T Bell Laboratories, untitled: A Technique for Drawing Directed Graphs', published in 1993 in IEEE Transactions on Software Engineering, ISSN: 0098-5589. The proposed technique describes a four-pass algorithm including an iterative heuristic for reducing edge crossing. Indeed, to be able to obtain good results in this domain, sophisticated iterative multi-pass algorithms combined with heuristics requiring the tuning of parameters need to be implemented.
In the airline industry, the visualization of airline routes is a function which has also a lot of applications. Although it is a highly useful function for professionals of this industry (e.g., to let them establish fares, to find alternate routes to a destination or just to have a view of a complete airline network) it is in practice rather poorly supported. Airline routes are nothing else but graphs where nodes are the cities and edges (i.e., the connections between nodes) the routes served by the various airline companies operating planes between any of the city airports around the world. The way routes are displayed by current airline software products often consists in getting an exhaustive list of all the paths in the network considered, an example of which is shown in FIG. 1 where cities are abbreviated by their 3-letter IATA (international air transport association) codes. It is really not that easy though to understand the structure of a particular graph of city nodes from its list of edges and paths.
The generalization of the use of graphic displays, even in industries where large reliable data centers are implemented from mainframe computers, potentially allows the display of graphs in graphic mode so as to make them more easily readable. These large data centers are those put in place, e.g., by any of a few global distribution systems (GDSs) that provide travel services to all the professionals of this industry including the traditional travel agencies. Such a GDS is for example AMADEUS, a European travel service provider with headquarters in Madrid, Spain. Often, monochrome ‘green-screen’ like display are still however in use, in an emulation mode, on modern personal computers or terminals that display text-only windows like the one shown in FIG. 1 (often, contrary to what is shown, on a dark background). In text-only mode the control of the software applications run from the above large data centers is then done by the professionals of this industry in a so-called cryptic mode through the use of esoteric control codes. This mode of controlling the travel software applications is however often preferred because it is in practice more efficient once the control codes and their parameters have been all learnt and kept in mind. Still, it has severe limitations, like having to display in text mode a connected graph of city nodes while a graphic display would be much more appropriate in this case.
However, as stated above, the drawing of graphs on a graphic display is not an easy task in itself. It requires the use of iterative multi-pass sophisticated algorithms possibly also requiring having to set heuristic parameters to tune the results.
Therefore, it is a main object of the invention to disclose a simple all-automated method of drawing graphs adapted to the display of airline routes and of other transportation means on a graphic display.
It is a specific object of the invention that the method neither requires the use of complex iterative algorithms nor the setting of heuristic parameters to always obtain easy-to-read display of graphs.
It is a further object of the invention that computation time of the method only grows linearly with the number of nodes to display.
Further objects, features and advantages of the present invention will become apparent to the ones skilled in the art upon examination of the following description in reference to the accompanying drawings. It is intended that any additional advantages be incorporated herein.